#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL a,b,p,t,x1;
map<LL,LL>tab;
LL qpow(LL a,LL b)
{
	LL ret=1;
	for(;b;b>>=1,a=a*a%p)
		if(b&1)ret=ret*a%p;
	return ret;
}
LL BSGS(LL y,LL z)
{
	y%=p;z%=p;
	tab.clear();
	LL m=ceil(sqrt(p)),k=z%p,temp=qpow(y,m);
	tab[z]=0;
	for(LL i=1;i<=m;++i)
	{
		k=k*y%p;
		if(!tab[k])tab[k]=i;
	}
	k=1;
	for(LL i=1;i<=m;++i)
	{
		k=k*temp%p;
		if(tab[k])return i*m-tab[k]+1;
	}
	return -1;
}
int main()
{
	LL T;
	scanf("%lld",&T);
	while(T--)
	{
		scanf("%lld%lld%lld%lld%lld",&p,&a,&b,&x1,&t);
		if(x1==t)
		{
			puts("1");
			continue;
		}
		if(!a)
		{
			if(b==t)puts("2");
			else puts("-1");
			continue;
		}
		if(a==1)
		{
			if(!b)puts("-1");
			else 
			{
				LL k=qpow(b,p-2);
				printf("%lld\n",((t-x1)+p)%p*k%p+1);
			}
			continue;
		}
		LL c=qpow(a-1,p-2),A=(x1+b*c%p)%p,B=(t+b*c%p)%p;
		printf("%lld\n",BSGS(a,B*qpow(A,p-2)%p));
	}
	return 0;
}
